#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
//class Solution
//{
//public:
//    void reseach(Node* root, vector<int>& v)
//    {
//        if (root == nullptr) return;
//        for (auto it = v.rbegin();it != rend();it++)
//        {
//            reseach(*it, v);
//        }
//        v.push_back(root->val);
//    }
//    vector<int> postorder(Node* root)
//    {
//        vector<int> v;
//        reseach(root, v);
//        return v;
//    }
//};
class Solution1
{
public:
    bool checkPartitioning(string s)
    {
        int n = s.size();
        if (n < 3) return false;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n;i >= 0;i--)
            for (int j = i;j < n;j++)
            {
                if (i == j) dp[i][j] = true;
                else if (((i + 1) == j) && s[i] == s[j]) dp[i][j] = true;
                else if (s[i] == s[j] && dp[i + 1][j - 1] == true) dp[i][j] = true;
            }
        for (int i = 1;i <= n - 2;i++)
            for (int j = n - 2;j >= 1;j--)
                if (i <= j && dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
        return false;
    }
};
class Solution6
{
public:
    int minCut(string s)
    {
        int n = s.size();
        vector<vector<bool>> judge(n, vector<bool>(n));
        for (int i = n - 1;i >= 0;i--)
            for (int j = i;j < n;j++)
                if(s[i]==s[j])  judge[i][j] = i + 1 < j ? judge[i + 1][j - 1] : true;
        vector<int> dp(n);
        for (int i = 1;i < n;i++)
        {
            if (judge[0][i]) dp[i] = 0;
            else
            {
                for (int j = 0;j < i;j++)
                {
                    if (judge[j + 1][i]) dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[n - 1];
    }
};
class Solution8
{
public:
    int longestPalindromeSubseq(string s)
    {
        int n = s.size(), ret = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1;i >= 0;i--)
            for (int j = i;j < n;j++)
            {
                if (i == j) dp[i][j] = 1;
                else if (i + 1 == j && s[i] == s[j]) dp[i][j] = 2;
                else
                {
                    
                }
                ret = max(ret, dp[i][j]);
            }
        return ret;
    }
};
class Solution {
public:
    int minInsertions(string s)
    {
        int n = s.size();
        vector<vector<bool>> judge(n, vector<bool>(n));
        for (int i = n - 1;i >= 0;i--)
            for (int j = i;j < n;j++)
                if (s[i] == s[j]) judge[i][j] = i + 1 < j ? judge[i +1 ][j -1 ] : true;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 1;i >= 0;i--)
            for (int j = i;j < n;j++)
            {
                if (i == j) dp[i][j] = 0;
                dp[i][j] = dp[i + 1][j - 1];
                if (s[i] != s[j]) dp[i][j] += 2;
            }
        return dp[0][n - 1];
    }
};
int main()
{
    string s = "mbadm";
    Solution().minInsertions(s);
	return 0;
}